package com.wp.targetOffer;

import java.util.ArrayList;
import java.util.Stack;

/**
 * Created by 王萍 on 2017/3/7 0007.
 */
public class 从尾到头打印链表 {

    public static void main(String[] args) {

        从尾到头打印链表 sample = new 从尾到头打印链表();

        ListNode listNode = new ListNode(1);
        ListNode listNode1 = new ListNode(2);
        ListNode listNode2 = new ListNode(3);

        listNode.next = listNode1;
        listNode1.next = listNode2;

        System.out.println(sample.printListFromTailToHead(listNode));
        System.out.println(sample.printListFromTailToHead2(listNode));
    }

    //借助栈先出后进的特性
    //简单的这里可以不用stack，用Collections.reverse(List list)方法。
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {

        ArrayList<Integer> integers = new ArrayList<>();
        Stack<Integer> stack = new Stack<>();

        while (listNode != null) {
            stack.push(listNode.val);
            listNode = listNode.next;
        }

        while (!stack.isEmpty()) {
            integers.add(stack.pop());
        }
        return integers;
    }


    ArrayList<Integer> integers = new ArrayList<>();
    //使用递归
    //实际上递归也是使用了堆栈。
    public ArrayList<Integer> printListFromTailToHead2(ListNode listNode) {

        //ArrayList需要放在方法的外部，否则每次递归都生成一个新的ArrayList
        ArrayList<Integer> integers = new ArrayList<>();
        if (listNode != null) {
            printListFromTailToHead2(listNode.next);
            integers.add(listNode.val);
        }
        return integers;
    }


    private static class ListNode {
        int val;
        ListNode next = null;

        public ListNode(int val) {
            this.val = val;
        }
    }
}

